The approaches described in this section could be pursued, but are not necessarily approaches that previously have been conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Computers may communicate with each other through a network by sending data packets to each other. While there are numerous protocols according to which one computer may address a data packet to another computer, a protocol commonly used for this purpose is Internet Protocol (IP). Typically, a data packet that is structured according to IP (an “IP data packet”) contains a source IP address and a destination IP address. By examining a destination IP address contained in an IP data packet, a network device can determine the identity of a computer to which the IP data packet ultimately should be transmitted.
The computer that originates an IP data packet (the “originating computer”) is often not directly connected to the computer for which the IP data packet is destined (the “destination computer”). The originating computer and the destination computer often transmit IP data packets through several interconnected intermediate network devices, such as network routers. Each router maintains a routing table that contains information that the router uses to select one of potentially several directly connected network devices to which the router should forward an IP data packet. Because each such directly connected network device is connected to a port of the router, the router selects one of potentially several ports through which to forward the IP data packet.
By communicating the information in their routing tables to other routers and updating their routing tables based on information received from other routers, routers can attempt to “learn” from each other the network routes from different sources to different destinations. Routers communicate such routing table information using a routing protocol. Some examples of routing protocols are distance vector protocols, such as Routing Information Protocol (RIP), and link state protocols, such as Open Shortest Path First (OSPF) protocol. RIP is described in the Internet Engineering Task Force (IETF) Request For Comments (RFC) 1058. OSPF is described in IETF RFC 1247.
According to past approaches, once a router learned which port to select given a particular destination IP address, the router would always select that port when given that particular destination IP address until the router learned, through a routing protocol, that it should select a different port when given that particular destination IP address. Upon learning a new port to select given a particular destination IP address, the router would always select the new port when given that particular destination IP address, and would not continue to select the old port when given that particular destination IP address. In other words, there was nothing random about which port a router would select given a particular IP address; the selection was deterministic.
Deterministic selection suffers from some significant disadvantages. While the routing protocols described above can be used to teach a router to select a different port in the event that a network device connected to a particular port fails or is disconnected from the network, the routing protocols described above propagate information only slowly, potentially resulting in a temporary interruption in network communication. Furthermore, because only one port is selected for a particular destination IP address, a surge in data packet traffic to a particular destination IP address could overload the transmission capacity of the port, even while spare transmission capacity is available on other ports through which the particular destination IP address ultimately might be reached.
DiGaro, G. and Dorigo, M. (1998) “Ant Net: Distributed Stigmergetic Control for Communications Networks,” Journal of Artificial Intelligence Research (JAIR), 9:317-365, describes a theoretical probabilistic routing approach. This “Ant Net” approach is modeled after the behavior of ants, which determine a best route to a destination by stochastically selecting between routes based on pheromones deposited on those routes by other ants. As more ants follow a particular route, more pheromones are deposited on the particular route relative to other routes. As more pheromones are deposited on a particular route, more ants are likely to select the particular route over other routes. However, because the ants' behavior is probabilistic, there is always a chance that an ant may select a route other than the route on which the most pheromones have been deposited, thus increasing the probability that other ants will also select that other route.
While the Ant Net approach theoretically describes probabilistic routing, it lacks details on how to overcome some significant obstacles that are present in actually implementing such an approach in large networks. According to the Ant Net approach, every network device in a network participates in the routing protocol, and every network device—whether or not a router—has an entry in each router's routing table. Following this approach, routing tables of routers in large networks would be huge and unmanageable. Furthermore, the Ant Net approach does not provide a mechanism that accounts for the addition or removal of network devices from the network. In dynamic networks, the addition and removal of network devices is common.
Additionally, the Ant Net approach uses “mobile agents” to gather network information and update routing tables. A mobile agent is a packet that includes executable code in addition to data. The communication of executable code in addition to data consumes more network bandwidth than the communication of data alone. Allowing a router to execute code contained in a packet potentially compromises network security.
Based on the foregoing, there is a clear need for a method for quickly and securely updating probabilistic routing information in a network while keeping routing tables at a manageable size. There is a particular need for such a method for use in large, dynamic networks.